1. Field of the Invention
The field of the invention relates generally to error correction and more particularly to a pipeline decoder that can be used to decode Reed-Solomon codes, for example.
2. Background
Today's digital systems, such as data transmission and storage systems, typically need to be efficient and reliable. As large, high speed data networks become more widely used and integral with day to day activities, individuals likely will depend more upon the efficient and reliable reproduction of the data that these networks transmit. To achieve such an efficient and reliable operation, digital systems typically use techniques for controlling errors and to ensure reliable data reproduction. Reed Solomon ("RS") codes have been used in digital systems to provide error control, including both error detection and error correction. Such systems have included, for example, space telecommunication systems, compact disc systems and digital telecommunication systems.
A Reed Solomon code consists of a set of code words. Each code word contains data and error correcting information. A code word is characterized by a total number of symbols N which include data symbols and parity symbols. Each symbol is m bits of binary data where m might be 8, for example. In a Reed Solomon code that uses m bit symbols, N is often chosen such that N=2.sup.m -1. Of the total number of symbols N, K of the symbols are data symbols. Accordingly, N-K of the symbols are parity symbols. Reed Solomon codes are typically designed to detect or detect and correct a predetermined number of errors. A code designed to detect and correct up to t errors in each N symbol code word, for example, typically requires K=2t parity bits. Reed Solomon codes are commonly described as (N,K) Reed Solomon codes to communicate the values N and K of the particular code.
Reed Solomon codes word by encoding data according to certain predetermined rules to produce encoded data having a known format. The encoded data might then be transmitted to a receiver, for example. The data that is transmitted shall be referred to as the transmitted data. The receiver, knowing the predetermined rules and the known format, often can detect errors in the received data by comparing it to the known format. If any differences exist, an error has occurred. Using certain rules, the receiver often can correct errors detected in this manner. After such correction, the corrected data can then be converted back from its encoded format to obtain the original data. The process of detecting or detecting and correcting errors and converting the encoded data back to its original form is called decoding. See Lin, S. and Costello, D. Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall (1983) for a discussion of Reed Solomon error correction and its related principles.
Numerous calculations can be required to perform the encoding and decoding processes associated with RS codes. In addition, these calculation often must be performed in real time. Accordingly, RS encoders and decoders often must meet certain minimum performance levels. With respect to RS decoders, efforts have been made to produce algorithms and/or techniques that enable the calculations to be performed quickly. Unfortunately, increasing the speed of RS decoders can also increase the cost.
For example, the speed of a decoder might be enhanced by using parallel architectures or large memory arrays. A parallel architecture may involve implementing the same functions in multiple areas of a chip. These multiple areas may be used, for example, when the same function, such as a calculation, needs to be performed repeatedly. Often, the repeated functions can be accomplished simultaneously in the multiple areas saving time. Unfortunately, implementing the same function in multiple areas typically requires more chip area than simply using a single chip area repeatedly to perform the single function. This latter approach, while possible saving chip area, can result in delay because the one chip area typically will have to perform the function multiple times. A batch of data that is to be processed by the chip area may have to wait until the chip area is done performing the function on a previous batch of data. Additionally, such repeated use might require additional control circuitry to handle timing or feedback issues, for example, and as a result additional chip space. Such a design might also require additional clock cycles and possibly addition buffers to store interim calculations.
Memory arrays might be used by an RS decoder to store data or look up tables that might eliminate some of the needed calculations, for example. Memory arrays, however, can increase the amount of chip area used by a decoder, resulting in a more expensive decoder. The chip are required by an RS decoder might be reduced by avoiding such parallel architectures or memory arrays. Such a decoder might be less expensive, but it may not provide the desired speed.
Accordingly, there has been a need for a Reed-Solomon decoder that obtains the desired processing speed without unacceptably increasing the chip area used by or the cost of the decoder.